package org.nowcoder.leetcode.twoPointers;

/**
 * Title  : 88. Merge Sorted Array
 * Source : https://leetcode.cn/problems/merge-sorted-array/?envType=study-plan-v2&envId=top-interview-150
 * Author : XrazYang
 * Date   : 2023-07-04
 */
public class LeetCode_88 {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //暴力解法： 先合并，再排序
        // for (int i = 0; i < nums2.length; i++) {
        //     nums1[m + i] = nums2[i];
        // }
        // Arrays.sort(nums1);

        //优化解法：利用有序特性，双指针法，O（m+n），空间复杂度O（m）
        int[] nums = new int[m];
        for (int i = 0; i < m; i++) {
            nums[i] = nums1[i];
        }
        int i = 0, j = 0, k = 0;
        while (i < m && j < n) {
            if (nums[i] <= nums2[j]) {
                nums1[k++] = nums[i++];
            } else {
                nums1[k++] = nums2[j++];
            }
        }
        if (i < m) {
            for (int l = i; l < m; l++) {
                nums1[k++] = nums[l];
            }
        }
        if (j < n) {
            for (int l = j; l < n; l++) {
                nums1[k++] = nums2[l];
            }
        }
    }
}
